package Top200;

/**
 * @author zhangmin
 * @create 2022-02-26 15:29
 * 遍历s1中的所有分割点，判断其是否是可扰乱的点
 */
public class isScramble87 {

    int[][][] memo;
    String s1,s2;
    //判断s1从i1开始，s2从i2开始，长度为len的子串包含的字符数量是否对应相等
    boolean iscountequal(int i1,int i2,int len){
        int[] count1=new int[26],count2=new int[26];
        for (int i = i1; i < i1+len; i++) {
            count1[s1.charAt(i)-'a']++;
        }
        for (int i = i2; i < i2+len; i++) {
            count2[s2.charAt(i)-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (count1[i]!=count2[i])
                return false;
        }
        return true;
    }
    //计算s1从i1开始，s2从i2开始长度为len的子串是否互为扰动字符串
    boolean dp(int i1,int i2,int len){
        String sub1 = s1.substring(i1, i1 + len);
        String sub2 = s2.substring(i2, i2 + len);
        if (memo[i1][i2][len]!=0) return memo[i1][i2][len]==1;

        if (sub1.equals(sub2)) {
            memo[i1][i2][len]=1;
            return true;
        }
        if (!iscountequal(i1,i2,len)){
            memo[i1][i2][len]=-1;
            return false;
        }
        //遍历所有可能的分割点k
        for (int k = 1; k < len; k++) {
            if (dp(i1,i2,k)&&dp(i1+k,i2+k,len-k)){
                //说明s1的两个字串在k处不交换就是扰动的字符串了
                memo[i1][i2][len]=1;
                return true;
            }
            if (dp(i1,i2+len-k,k)&&dp(i1+k,i2,len-k)){
                //两个字串交换后成为扰动字符串
                memo[i1][i2][len]=1;
                return true;
            }
        }
        memo[i1][i2][len]=-1;
        return false;
    }

    public boolean isScramble(String s1, String s2) {
        memo=new int[s1.length()][s2.length()][s1.length()+1];
        this.s1=s1;this.s2=s2;
        return dp(0,0,s1.length());
    }
}
